编译原理
编译原理
一、编译器概述
1.1 定义
编译器是一个程序,完成由源代码=>目标代码
解释器也是一种处理程序的一种程序,它直接输出程序的结果并不是可执行文件
1.2 编译器核心功能
生成的目标代码和原代码语意相同
1.3 编译器简史
Fortran是第一个编译器
为什么要学习编译原理?
编译原理集中体现了计算机科学的很多核心思想
- 算法,数据结构,软件工程等
....
1.4 编译器结构
- 具有非常模块化的高层结构
前后端:前端为输入代码、后端指如何将前端映射到指令集
前端:词法分析、语法分析
后端:指令生成、指令优化
通过符号表进行交互
偏译器由多个阶段组成,每个阶段都要处理不同的问题,所以需要合理的划分组织各个阶段
- 接口清晰
- 编译器容易实现、维护
eg:
前端生成一个语法生成树,然后后端根据规则生成代码,例如此加法通过后续遍历,如果是数字就push,‘+’就执行add
整体流程:前端=>中间表示=>中段=>后端=>代码
中段主要负责优化
二、词法分析
2.1 词法分析的任务
词法分析器作用:字符流=>记号流
字符流:和被编译的语言密切相关(ASCII,Unicod....)
记号流:编译器内部定义的数据结构,编码所识别出的词法单元
记号的数据结构定义:关键词与关键词的值
2.2 词法分析器的手工构造
2.2.1 词法分析器分类
实现词法分析器方案:手工编码实现法、词法分析器的生成器
2.2.2 转移图
理解手工构造的核心问题是转移图
例如识别符号的转移图
实现代码
2.2.3 标识符的转移图
例如c语言中的变量名
2.3 自动生成词法分析器
2.3.1 正则表达式
通过声明式的规范,可以通过正则表达式。
声明式规范:正则表达式
词法分析器:有限状态自动机(DFA)
正则表达式定义:
例如在c语言中,字符集则是 ASCII
正则表达式的形式表示:
标识符:第一部分字符或下划线,第二部分加上数字且可能有多个即闭包
无符号整数:(十进制整型数)或者是0;或者是以1到9开头,后跟零个或多个0到9 => 0|【(1|…|9)(0|…|9)*】
2.3.2 语法糖
概念:通过抽象一些概念使得程序编写更加容易
e? === e | 空串
2.3.3 有限状态自动机
FA 判断输入的字符串能否识别,能识别就回复 yes
接收的概念是输入的字符串是指能到达接受(终止)状态(双圈)
非确定有限状态自动机 NFA:不确定的含义是,存在这样的状态,对于某个输入符号,它存在不止一种转换。接受状态较难判断,一般转换为 DFA 后判断是否接受
确定有限状态自动机 DFA:确定的有限自动机从任何状态出发,对于任何输入符号,最多只有一个转换。
2.3.4 DFA 的实现
带有边和节点有向图
三、RE=>NFA
从正则表达式=>非确定转换机
3.1 RE=>NFA Thompson
对基本的RE直接构造,对复合的RE递归构造。递归算法,容易实现
e转化:本质上是说0=>1不需要吃掉字符串,没有任何代价
复合RE自动机状态 e1 e2
e1 | e2
例子:
a(b|c)*
3.2 NFA=>DFA 子集构造算法
NFA与DFA接受的字符串要完全等价
先任意输入字符串
例如 n0=>n1 输入a,但n1可通过e到{n1,n2,n3,n4,n6,n9} (即求e闭包) 得到边界q1
q1 输入 b 可以到 n5, 得到边界 q2
依次推出所有边界集合
子集构造算法代码
算法不可能无限循环
时间复杂度最坏
N表示NFA状态节点个数
3.2.1 eps闭包的计算
通过深度优先算法
sq q
3.3 DFA 最小化 Hopcroft算法
3.4 DFA生成分析算法
先生成 DFA 代码表示 (转移表类似于邻接矩阵)
驱动代码 输入字符串后可判断识别
3.4.1 最长匹配
四、语法分析
4.1 语法分析任务
早期语法分析只判断,是否有语法错误,后续语法分析演变成生成抽象生成树
需要语法规则来判断是否符合语言规则
使用语法树
4.2 上下文无关文法
4.2.1 概念
总共四类文法: 三性=>零性文法:正则表达式=>上下文无关文法=>上下文有关文法=>任意文法
上下文无关法本来是用来描述自然语言的,用来形式化自然语言
S(句子) => N(名词) V(动词) N(名词)
上下文无关文法G = (T,N,P,S) 是一个四元组
T:是终结符集合 N: 终结符 P:一组产生规则 S:唯一的开始符号
所有终结符都是大写符号
4.2.2 推导
不停的替换非终结符,直到句子全是终结符停止。
- 最左推导:每次总是选择最左侧的符号进行替换
- 最右推导:每次总是选择最右侧的符号进行替换
语法分析器需要做什么:给定文法G和句子s(无非终结符叫句子),判断是否存在对句子s的推导
4.3 分析树和二义性
4.3.1 分析树
推导得到对应的分析树,推导得到分析树和推导顺序无关(最左最右...)
特点:
- 树中的每个内部节点代表非终结符
- 每个叶子节点代表终结符
- 每一步推导代表如何从双亲节点生成它的直接孩子节点
树的每一层往下都代表一次替换,最终叶子节点表示终结符。树的意义通过后续遍历来表达。
因此两颗树产生了二义性
4.3.2 二义性文法
给定文法G,如果存在句子s,它有两棵不同的分析树,那么称G是二义性文法。
解决方式:文法分析
- 表达式文法的重写
4.4 自顶向下分析
语法分析:给定文法G和句子s,回答s是否能够从G推导出来?
基本算法思想:从G的开始符号出发,随意推导出某个句子t比较t和s
若t==s
,则回答“是”
若t!=s
,并不能直接返回“否”,可能是推导顺序不对需要回溯
从开始符号出发推出句子,因此是自顶向下
伪代码实现:
注意压栈的时候需要逆序压入。
此种算法效率太低,需要一种线性时间算法,避免回溯。
因此引入递归下降分析算法,和 LL(1)分析算法
- 前看符号避免回溯
4.5 递归下降分析算法
也称预测分析算法
- 分析高效(线性时间)
- 容易实现(方便手工编码)错误定位和诊断信息准确
- 被很多开源和商业的编译器所采用 GCC 4.0,LLVM...
算法基本思想:分治法
- 每个非终结符构造一个分析函数
- 用前看符号指导产生式规则的选择
如果是终结符就判断是否相等,否则递归调用非终结符的分析函数
eg: x=> a B
parse_x() token==a;
parse_B();
error()
4.5.1 出现两种转化都可以辨别时如何处理
当输入 num 时 E转化两种形式都可以识别当前的字符
4.5.2 错误分析
递归向下分析算法必须具有调整机制
-
插入单词
插入单词来进行错误恢复是一种危险的做法,可能插入会进一步导致其他错误,陷入死循环。插入法不必对实际的输入调整,假装存在某个单词,输出错误信息,然后返回即可。
-
删除单词
跳过若干个单词直至达到一个属于 FOLLOW 集合的单词为止。
4.6 LL(1)分析算法
总结来说:算出 First集和FOLLOW集,对应每一条产生式,求出每条产生式的Select集,当产生式能推出空串的时候需要将follow集加入到此情况中,其他按照first集来计算
从左(L)向右读入程序,最左(L)推导,采用一个(1)前看符号就叫做LL(1)分析算法,是一种自顶向下分析算法
- 分析高效(线性时间)
- 错误定位精确
- 有很多开源或商业的生成工具:ANTLR
算法思想:基于表驱动的分析算法
思想等同于自顶向下分析算法
问题转化为判断什么是正确的符号,然后将其压入栈中,这样避免了回溯
横表示非终结符,列表是此符号开头,数组的值代表正确的转换方式
分析表,数组的值代表对应的转化规则,当匹配到相应的规则时,压入对应的字符
4.6.1 FIRST集的不动点算法代码
从非终结符N开始推导得出的句子开头的所有可能的终结符的集合,得到FIRST集(开始集)
FIRST集的不动点算法
对应文法产生的FIRST集
# 0:S -> N V N
# 1:N -> s
# 2: | t
# 3: | g
# 4: | w
# 5:V -> e
# 6: | d
foreach(nonterminal N)
FIRST(N) = {} # init FIRST(N) = {} 初始化每个集合为空
while(some set is changing) // 当每一轮中有集合发生了变化继续循环
foreach(production p: N -> b1, b2 ..... bn) # 对于N的每一个生成式
if(b1 == a....)
FIRST(N) U= {a}
else if(b1 == M....)
FIRST(N) U= FIRST(M)
N\迭代次数 | 0 | 1 | 2 | 3 |
---|---|---|---|---|
S | {} | {} | ||
N | {} | |||
V | {} |
当我们把FIRST推向所有字符串的时,即不局限于非终结符。
FIRST_S(b1,b2,b3.....bn) // Sentences句子
FIRST(N) IF b1 == N
{a} IF b1 == a
这样就得到了所有转化关系的FIRST集,因此构造出分析表。
且得出LL(1)定义,如果分析表中每个表项都只有一个值,则成其为LL(1)文法
非终结符\终结符 | s | t | g | w | e | d |
---|---|---|---|---|---|---|
S | 0 | 0 | 0 | 0 | ||
N | 1 | 2 | 3 | 4 | ||
V | 5 | 6 |
如果是集合S,那么将所有FIRST(S)集合中的元素填入对应的转化关系编号到表中
4.6.2 分析表中的冲突
分析表中表项有超过一个的情况会产生冲突
非终结符\终结符 | s | t | g | w | e | d |
---|---|---|---|---|---|---|
S | 0 | 0 | 0 | 0 | ||
N | 1 | 2 | 3 | 4、5 | ||
V | 6 | 7 |
# 0:S -> N V N
# 1:N -> s
# 2: | t
# 3: | g
# 4: | w => {w}
# 5: | w V => {w}
# 6:V -> e
# 7: | d
此情况两种转化式都满足w开头,因此可能再次出现回溯
对N的两条产生式规则N=>β和N=>γ,要求FIRST_S(β)∪FIRST_S(γ)=={},如果不为空集则会产生冲突
4.6.3 一般条件下的LL(1)文法
FIRST_S(XYZ)
- 一般情况下需要知道XY是否可为空串,NULLABLE
- 且需要知道某个非终结符后面跟着什么符号,跟随集FOLLOW
NULLABLE集合定义:**非终结符x**属于集合NULLABLE,当且仅当:
# 基本情况
# X -> eps # e为空串
# 归纳情况
# X -> b1 b2 ... bn
当且仅当b1 b2 ... bn都属于NULLABLE时,X才为NULLABLE
得到NULLABLE集合的算法
NULLABEL = {} # init nullable
while(nullable is still change)
foreach(production p: X -> b) // 遍历每条产生式
if(b == e)
NULLABLE U= {X}
else if (b == Y1, Y2, .... Yn) //注意 Yn 也要是NULLABLE
if(Y1 属于 NULLABLE && Y2 属于 NULLABLE && .....)
NULLABLE U= {X}
0 | 1 | 2 | |
---|---|---|---|
NULLABLE | {} |
# Z -> d
# | X Y Z
# Y -> c
# | e # e为空串
# X -> Y
# | a
有了NULLABLE便可推FIRST集合的完整计算公式
# 基本情况:
X -> a #是终结符的情况
FIRST(X) U= {a}
# 归纳情况:
X -> Y1,Y2,Y3...Yn
FIRST(X) U= FIRST(Y1)
if Y1 属于 NULLABLE
FIRST(X) U= FIRST(Y2)
if Y1, Y2 属于 NULLABLE
FIRST(X) U= FIRST(Y3)
.......
得到伪代码
foreach(nonterminal N)
FIRST(N) = {}
while(some set is changing)
foreach(prduction p: N->b1,b2,b3...bn)
foreach(bi from b1 to bn)
if (bi == a...)
FIRST(N) U= {a}
break
if (bi == M...)
FIRST(N) U= FIRST(M)
if(M not in NULLABLE)
break
//else // 如果M是在NULLABLE中需要加上其后面跟着符号的FIRST集合 可以不写让他继续遍历下去
// FIRST(N) U= FOLLOW(M)
N\FIRST | 0 | 1 | 2 | 3 |
---|---|---|---|---|
Z | {} | |||
Y | {} | |||
X | {} |
FOLLOW集合的不动点算法
foreach( nonterminal N)
FOLLOW(N) = {} # init nonterminal N
while(some set is changing) // 注意计算非终结符follow集并不是单独计算的,在每个产生式中都需要执行每一个符号
foreach(production p: N -> b1, b2, b3.... bn)
temp = FOLLOW(N) # temp一开始代表N的结束后跟着的集合 每一次都往前移
foreach(bi from bn to b1) # 逆序!
if(bi == a ...)
temp = {a}
if(bi == M ...)
FOLLOW(M) U= temp
if(M is not NULLABLE)
temp = FIRST(M) # M不能为空当前得到的FOLLOW只能是M的开头
else
temp U= FIRST(M) # M可以为空所以当前得到的FOLLOW是 FIRST(M) + 原来temp
根据此算法得出非终结符的FOLLOW集合
N\FOLLOW | 0 | 1 | 2 |
---|---|---|---|
X | {} | {} | {} |
Y | {} | ||
Z | {} |
得到了NULLABLE和FOLLOW最终得出 FIRST_S 的算法
foreach(production p)
FIRST_S(p) = {}
calculte_FIRST_S(production p: N -> b1, b2, ... bn)
foreach(bi from b1 to bn)
if(bi == a ...) # 第一个符号是终结符就直接加入FIRST_S 并返回函数结束
FIRST_S(p) U= {a}
return
if(bi == M ...)
FIRST_S(p) U= FIRST(M) # 非终结符计算对应的FIRST(M)
if(M is not NULLABLE) # 如果可以为空则需要继续看后面的符号 继续foreach
return
FIRST_S(p) U= FOLLOW(N) # 如果上面始终没有返回代表全部可以为空,则需要加上FOLLOW(N)集合
4.6.4 回看分析表中的冲突
消除左递归可以解决冲突,任何有左递归的文法都不是LL(1)文法
#0:E -> E + T #0: E -> TE'
#1: | T #1: E'-> +TE'
#2:T -> T * F => #2: |
#3: | F #3: T -> FT'
#4:F -> n #4: T'-> *FT'
#5: |
#6: F -> n
n | + | * | |
---|---|---|---|
E | 0 | ||
E’ | 1 | ||
T | 3 | ||
T’ | 5 | 4 | |
F | 6 |
提取左公因子
# 0: X -> aY
# 1: | aZ
# 可以通过提取公因子的方法,比如对上述文法提取一个{a}.就可变为
# 0: X -> aX'
# 1: X'-> Y
# 2: | Z
也可以解决一定冲突
4.7 LR(0)
LL(1)分析文法有限,往往需要文法的改写.
LR分析算法(移进-归约算法),是一种自底向上分析算法。
- 从左(L)向右读入程序,最右(L)推导,不用前看符号来决定产生式的选择(0个前看符号)
产生式从左到右称为推导,从右到左称为归约
是一个最右推导的逆过程,需要两个步骤。
点左边代表已经读入栈中,点号的右侧是待输入的字符
-
移进 一个记号到栈顶上,或者
-
归约 栈顶上的n个符号(某产生式的右部)到左部的非终结符(当我们发现一个原点到达项的末尾)
对产生式 A->β1 ...βn
如果βn ... β1在栈顶上,则弹出βn...β1压入A=---------------
4.7.1 移进和归约的时机
利用一个有记忆能力的自动机帮助我们匹配字符
加入一个项目集合: 带有·号的产生式
shift 2 表示到达2状态
reduce 2 表示利用产生式2进行归约
分析 : x x y $
起始状态 : * x x y $ # 开始点的左侧没有读入
1 x * x y $ # 开始后读入第一个字符x ,并且是从1号状态开始的
1 x 2 x 3 y 4 * $ # 读入 x 后到达状态2压入栈中,后面同理
1 x 2 x 3 T * $ # 当到达$后需要开始归约
1 x 2 x 3 T 5 * $ # 3 T => 5 则压入并且开始归约 x x T
1 S * $ # 1 S => 6 是一个终止状态则成功匹配
stack = []
push ($) // $: end of file
push (1) // 1: initial state
while (true)
token t = nextToken()
state s = stack[top]
if (ACTION[s, t] == "si")
push (t);
push (i)
else if (ACTION[s, t] == "rj")
pop (the right hand of production "j: X -> B")
state s = stack[top]
push (X);
push(GOTO[s, X])
else error (…)
4.7.2 LR(0)分析表构造算法
4.8 SLR分析算法
LR(0)会延迟发现错误,并且可能发生冲突
-
延迟错误发现的时机
在归约的时候并不看后面跟着的字符直接归约,可能是无用功
-
冲突情况
在这种情况下当到达状态3时,两周产生式分别对应移进,和归约产生冲突
引入 SLR 算法:
整体步骤和LR(0)步骤相同,区别仅在归约步骤上。
- 对于状态i上的项目 X=> α*, 仅对 y ∈ FOLLOW(X)的情况添加ACTIVE[i,y] = "rk"
4.9 LR(1)分析算法
SLR仍然可能有冲突
4.9.1 LR(1) 的项目
项目变成了二元,意味着当只有当输入a时需要归约,其他情况不填入 ACTION
4.9.2 处理二义性文法
LR(1)并不能处理二义性文法,但我们可以通过设置优先级,左结合,单挂else等来达到处理二义性文法的效果
4.10 基于LR(1)的分析工具
YACC是Yet Another Compiler Compiler缩写,代表编译器的编译器
4.11 语法制导翻译
语法分析需要在判断是否合法外,还可能需要完成:
- 类型检查
- 目标代码生成
- 中间代码生成
- ....
这些都通过语法制导完成
4.11.1 语法制导翻译的基本思想
视频p69 详细观看
- 给每条产生式规则附加—个语义动作
- 一个代码片段
- 语义动作在产生式“归约”时执行,即由右部的值计算左部的值
归约的时候通过右部得出左部的值
在归约之前先执行语义动作,即计算出表达式。
state是当前所属自动机状态
4.12 抽象语法树
生成抽象语法树,存储在内存中,供后续使用
4.12.1 分析树
对于表达式而言,编译只需要知道运算符和运算数
- 优先级、结合性等已经在语法分析部分处理掉了
对于语句、函数等语言其他构造而言也一样
- 例如编译器不关心是=还是:=
分析树上有一些无关的信息,加大不必要的存储,需要抽象
早期编译器不生成语法树,但现代编译器通过抽象语法树作为语法分析的输出
- 更好的系统支持
- 简化编译器设计
4.12.2 语法树具体实现
E => n
| E + E
| E * E
数据结构定义:
4.12.3 抽象语法树的自动生成
五、语法制导
5.1 语法制导概念
定义:语法分析+语义分析+中间代码生成 => 语法制导翻译
使用上下文无关文法来引导对语言的翻译,是一种面向文法的翻译技术
5.1.1 基本思想
如何表示语义信息?
为上下文无关文法符号设置语义属性。通过相关语义规则进行计算语义属性
5.1.2 语法制导定义 SDD
定义: 用于将语义规则和产生式关联( 语法制导定义 是一个上下文无关文法和属性及规则的结合)
a是X的属性,则用X.a表示某个标号为X的分析树结点上的值
构造一个二进制语法制导定义(即计算方案):语法制导定义
5.1.3 语法制导翻译方案 SDT
5.2 SDD
5.2.1 文法符号的属性
综合属性:在分析树结点N上的非终结符A的综合属性只能通过N的子结点或N本身的属性值来定义
继承属性:在分析树结点N上的非终结符A的继承属性只能通过N的父结点、N的兄弟结点或N本身的属性值来定义
终结符也可以有综合属性,终结符的综合属性是由词法分析提供的词法值,因此SDD中没有计算终结符的语义规则。没有继承属性
语义规则可能会带有副作用
5.2.2 属性文法
定义:一个没有副作用的SDD有时也称为属性文法
- 属性文法的规则仅仅通过其它属性值和常量来定义一个属性值
右侧语义规则为属性文法
5.2.3 SDD求值顺序
语义规则建立了属性之间的依赖关系,在对语法分析树节点的一个属性求值之前,必须首先求出这个属性值所依赖的所有属性值
依赖图:依赖图是一个描述了分析树中结点属性间依赖关系的有向图。如果属性X.a的值依赖于属性Y.b的值,则依赖图中有一条从Y.b的结点指向X.a的结点的有向边
有副作用,设置一个虚综合属性。继承属性在节点的左侧,综合属性在节点右侧。
计算顺序需要满足求依赖者时,被依赖者全部被求出=>引入拓扑排序(即先输出出度为0的结点)
需要注意有环情况的产生则可能无法判断计算顺序。
5.3 S、L属性定义
5.3.1 S属性
定义:仅仅使用综合属性的SDD称为S属性的SDD,或S-属性定义、S-SDD
5.3.2 L属性
L-属性定义:在一个产生式所关联的各属性之间,依赖图的边可以从左到右,但不能从右到左(L属性(Inherited Attribute))。 (综合属性不受限制,看继承属性是否是左侧或本身属性)
正式定义:
一个SDD是L-属性定义,当且仅当它的每个属性要么是一个综合属性,要么是满足如下条件的继承属性:
假设存在一个产生式A→X1X2 .. Xn, 其右部符号Xi(1<i≤n)的继承属性仅依赖于下列属性:
- A的继承属性
- 产生式中Xi 左边的符号X1,X2,.... Xi-1 的属性
- Xi本身的属性,但 Xi 的全部属性不能在依赖图中形成环路
5.4 语法制导方案 SDT
定义:语法制导翻译方案(SDT)是在产生式右部中嵌入了程序片段(称为语义动作)的上下文无关文法
- SDT可以看作是SDD的具体实施方案
重点关注两种情况,可以使用SDT来实现两类重要的SDD
- 基本文法可以使用LR分析,且SDD是S属性的
- 基本文法可以使用LL分析,且SDD是L属性的
5.4.1 S-SDD转化为SDT
将一个S-SDD转换为SDT的方法:将每个语义动作都放在产生式的最后
5.4.2 L-SDD转化为SDT
将L-SDD转换为SDT的规则:
- 将计算某个非终结符号A的继承属性的动作插到产生式右部中紧靠在A的本次出现之前的位置上(左侧)
- 将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端(末尾)